package 比赛.jitiaojuesai;

import java.util.Scanner;

public class Test2 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int W = sc.nextInt();
        int n = sc.nextInt();

        int[] w = new int[n];
        int[] v = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
            w[i] = w[i] * v[1];
        }

        sc.close();
        System.out.println(func(w, v, W,n));


    }

    public static int func(int weight[], int value[], int w,int N) {

        int f[][] = new int[N + 1][w + 1];//列是物品的重量和价值，行是背包装的体积
        //当不放物品时
        for (int col = 0; col < w + 1; col++) {
            f[0][col] = 0;
        }
        //当背包体积是0时
        for (int row = 0; row < N + 1; row++) {
            f[row][0] = 0;
        }
        //其他的地方从第二行，第二列开始
        //一行一行填表
        for (int col = 1; col < N + 1; col++)//当前物品的重量weight[col-1] 当前物品的价值values[col-1]
        {
            for (int row = 1; row < w + 1; row++)//列代表背包当前容量
            {
                //比较当前物品的重量能否加入背包
                if (weight[col - 1] < row)//yes
                {
                    //比较不加入该物品时该重量的最大价值（前一行）与当前物品的价值+可以容纳的剩余重量的价值
                    //不加入当前物品的最优解为前一行f[col-1][row]
                    //加入当前物品后背包剩余的容量应该是剩余容量的最优解(在上一行)f[col-1][row-weight[col-1]]
                    f[col][row] = Max(f[col - 1][row], value[col - 1] + f[col - 1][row - weight[col - 1]]);
                } else//但前物品放不进就选当前容量的最优解即（上一行）
                {
                    f[col][row] = f[col - 1][row];
                }
            }
        }

        return f[N][w];
    }

    public static int Max(int x, int y) {
        if (x >= y)
            return x;
        else
            return y;
    }


}

